package com.peng.leetcode.sort;

import java.util.*;

/**
 * SortArrayByParityII
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
 * <p>
 * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
 *
 * @author: lupeng6
 * @create: 2020/12/10 16:42
 */
public class SortArrayByParityII {

    public static void main(String[] args) {
        int[] arr = {3, 4};
        int[] x = new Solution().sortArrayByParityII(arr);
        for (int i : x) {
            System.out.println(i);
        }
    }

    static class Solution {
        public int[] sortArrayByParityII(int[] A) {
            Deque<Integer> deque = new LinkedList<>();
            for (int i : A) {
                if (i % 2 == 0) {
                    deque.add(i);
                } else {
                    deque.push(i);
                }
            }
            int[] ret = new int[A.length];
            for (int i = 0; i < A.length; i++) {
                if (i % 2 == 0) {
                    ret[i] = deque.pollLast();
                } else {
                    ret[i] = deque.pollFirst();
                }
            }
            return ret;
        }
    }
}
